package LeetCode._01_树;
/**
 * https://leetcode-cn.com/problems/maximum-binary-tree/
 */
public class _654_最大二叉树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return maxTree(nums,0,nums.length-1);
    }

    //给定一个区间，创建并返回一个二叉树的根节点
    public TreeNode maxTree(int[] nums,int startIndex,int endIndex){
        if(startIndex>endIndex) return null;
        int index = -1;
        int rootVal = Integer.MIN_VALUE;
        for(int i=startIndex;i<=endIndex;++i){
            if(rootVal<nums[i]){
                rootVal = nums[i];
                index = i;
            }
        }
        //创建根节点
        TreeNode root = new TreeNode(rootVal);
        root.left = maxTree(nums,startIndex,index - 1);
        root.right = maxTree(nums,index + 1,endIndex);

        return root;
    }

}
